package com.hy.backtracking2;

import java.util.ArrayList;
import java.util.List;

public class SumOfCombine {


    /**
     * 39. 组合总和
     * 力扣题目链接
     *
     * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     *
     * candidates 中的数字可以无限制重复被选取。
     *
     * 思路
     * B站视频讲解-组合总和
     *
     * 题目中的无限制重复被选取，吓得我赶紧想想 出现0 可咋办，然后看到下面提示：1 <= candidates[i] <= 200，我就放心了。
     *
     * 本题和77.组合，216.组合总和III和区别是：本题没有数量要求，   可以无限重复，但是有总和的限制，    所以间接的也是有个数的限制。
     *
     * 本题搜索的过程抽象成树形结构如下：
     * 注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！
     *
     * @param candidates
     * @param target
     * @param idx
     * @return
     */
    public List<List<Integer>> combineSum(int [] candidates,int target,int idx){
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        combine(res,path,candidates,target,0,idx);
        return res;
    }


    public void combine(List<List<Integer>> res,List<Integer> path,int [] candidates,int target,int sum,int idx){

        if (sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target){
                break;
            }
            path.add(candidates[i]);
            combine(res, path, candidates, target, sum+candidates[i], idx);
            //回溯，移除路径 path 最后一个元素
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        int [] candidates ={2,3,7,8};
        SumOfCombine sumOfCombine = new SumOfCombine();
        System.out.println("res: "+ sumOfCombine.combineSum(candidates, 11, 0));

    }
}
